package Ch_2_2_Mergesort;

public class Practise_2_2_13 {
    public static void main(String[] args) {
        /*
         * 对于 N 个元素 { a1,a2, a3, a4 ... an }的可能出现的所有排列方式共计 N! 种
         * 比如 1 2 3 4 第一个位置有 4 种，第二个位置有 3 种，以此类推共计 4! = 24 种排列方式
         * 所以其中 a1 < a2 < a3 < a4 ... < an 的这种排列占总排列个数的  1 / N!
         * 每进行一次比较，就是把最终得到的一个叶子节点划分到了 ak < am 对应的路径，或者 ak >= am 对应的路径下
         * 因此可以构造出一棵基于比较的二叉树，所有叶结点都是我们最终得到的排列的一种可能，而除此外的节点
         * 代表了比较操作
         * 
         * 根据二叉树的性质，如果叶子节点有 N! 个，那么二叉树高度最少为 logN!，此时的二叉树是满二叉树
         * 因为从根结点到叶子结点的一条路径也就是树高代表了比较的深度，所以对于 N 个元素
         * 基于比较的排序算法最少比较次数为 logN!
         * 
         * 因为 N! = N * (N-1) * (N-2) * ... 1 < N^N
         * 所以 logN! < N * logN
         * 因为 N! = N * (N-1) * (N-2) * ... 1 > (N/2)^(N/2)
         * 所以 logN! > N/2 * log(N/2)
         * 因此 logN! 和 N * logN 的增长率相同，我们可以说基于比较的排序算法，至少需要 N * logN 次比较
         */
    }
}
